import java.util.Arrays;

/**
 * 归并排序算法
 * 时间复杂度 O(nlogn)
 * 空间复杂度 O(n)
 */
public class MergeSortAlgorithm {
    /**
     * 归并排序
     * @param array 待排序数组
     * @param tempArray 临时数组，用于存放待归并的数组
     * @param left 数组左边界
     * @param right 数组右边界
     */
    public static void mergeSort(int[] array, int[] tempArray, int left, int right){
        if(left < right){
            int mid = left + (right - left) / 2;
            mergeSort(array, tempArray, left, mid);             // 分
            mergeSort(array, tempArray, mid + 1, right);   // 分
            merge(array, tempArray, left, right, mid);          // 合并
        }
    }

    /**
     * 将两个有序子数组归并到新数组
     * @param array 待归并的数组，归并后的结果也通过这个数组返回
     * @param tempArray 临时数组，用于存放待归并的数组
     * @param _left 数组左边界
     * @param _right 数组右边界
     * @param _mid 两个数组的分界线 [_left, mid] [mid + 1, _right]
     */
    private static void merge(int[] array, int[] tempArray, int _left, int _right, int _mid){
        for(int i = _left; i <= _right; i++){
            tempArray[i] = array[i];
        }
        int index1 = _left;
        int index2 = _mid + 1;
        int i = _left;
        while(index1 <= _mid && index2 <= _right){
            if(tempArray[index1] <= tempArray[index2]){
                array[i] = tempArray[index1];
                i++;
                index1++;
            }else{
                array[i] = tempArray[index2];
                i++;
                index2++;
            }
        }
        while(index1 <= _mid){
            array[i] = tempArray[index1];
            i++;
            index1++;
        }
        while(index2 <= _right){
            array[i] = tempArray[index2];
            i++;
            index2++;
        }
    }

    public static void main(String[] args) {
        int[] array = new int[]{8, 7, 6, 5, 4, 3, 2, 1};
        int[] tempArray = new int[array.length];
        for (int value: array) {
            System.out.print(value + " ");
        }
        System.out.println();
        MergeSortAlgorithm.mergeSort(array, tempArray, 0, array.length - 1);
        for (int value: array) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}
